package _01_排序;

import java.util.Arrays;

/*
    归并排序,本质上一个二叉树的后序遍历,不断将数组化成子数组进行排序，最后不断地进行合并
 */
public class Merge {
    private static int[] temp; //用于辅助合并有序数组

    //对nums数组进行归并排序
    public static void sort(int[] nums){
        temp = new int[nums.length];
        //排序整个数组，原地(修改)
        sort(nums,0,nums.length-1);
    }

    //函数定义:将子数组nums[lo,hi]进行排序
    private static void sort(int[] nums,int lo,int hi){
        if(lo == hi) return; //单个元素不用排序

        //计算中间索引，用来不断将数组划分成若干个子数组，防止溢出
        int mid = lo + (hi - lo) /2;

        //先对左半部分数组nums[lo],nums[mid]排序
        sort(nums,lo,mid);
        //在对右半部分数组nums[mid+1],nums[end]排序
        sort(nums,mid+1,hi);

        //两个子数组排序后，对整体合并成一个有序数组
        merge(nums,lo,mid,hi);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int lo, int mid, int hi) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        //存放的是两个有序数组，但是未合并
        for(int i=lo;i<=hi;i++){
            temp[i] = nums[i];
        }

        //i指向左半边有序数组的起始，j指向右半边有序数组的起始
        int i = lo,j = mid + 1;
        for(int p = lo;p<=hi;p++){
            if(i == mid + 1){
                nums[p] = temp[j++];
            }else if(j == hi + 1){
                nums[p] = temp[i++];
            }else if(temp[i]>temp[j]){
                nums[p] = temp[j++];
            }else{
                nums[p] = temp[i++];
            }
        }

    }

    public static void main(String[] args) {
        int[] nums = {2,1,50,25,3,65,41,78,23,6,99,50,450,69};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
